home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / DEMOS / DDJZSORT.ZIP / ZSORT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-03-03  |  49.7 KB  |  1,564 lines
  1. /* clip.c
  2.  
  3.    Win32 program to demonstrate z-sorted spans.
  4.  
  5.    Derived from the VC++ generic sample application.
  6.    Tested with VC++ 2.0 running on Windows NT 3.5.
  7.  
  8.    Note: in this implementation, polygon faces must not be
  9.    interpenetrating. Also, correct sorting is not guaranteed
  10.    if two polygonal objects butt up against each other. In other
  11.    words, each polygonal object must be made of a continuous,
  12.    non-self-intersecting skin, and polygonal objects must not
  13.    interpenetrate or touch in order for proper sorting to result.
  14.    More complex, slower sorting is required to make those cases
  15.    work reliably.
  16.    
  17.    Note: polygon processing could be considerably more efficient
  18.    if polygons shared common edges and edges shared common vertices.
  19.    Also, indirection to vertices could be used to avoid having to
  20.    copy all the vertices during every clip test. Outcode-type
  21.    testing could be used to determine completely clipped or
  22.    unclipped polygons ahead of time, avoiding the need to clip and
  23.    copy entirely for such polygons. Outcode-type tests work best in
  24.    viewspace, with the frustum normalized so that the field of view
  25.    is 90 degrees, so simple compares, rather than dot products, can
  26.    be used to categorize points with respect to the frustum. See
  27.    _Computer Graphics_, by Foley & van Dam, or _Procedural Elements
  28.    of Computer Graphics_, by Rogers, for further information.
  29. */
  30.  
  31. #include <windows.h>       // required for all Windows applications
  32. #include <stdlib.h>
  33. #include <stdio.h>
  34. #include <math.h>
  35. #include "zsort.h"         // specific to this program
  36.  
  37. #define INITIAL_DIB_WIDTH      320        // initial dimensions of DIB
  38. #define INITIAL_DIB_HEIGHT    240        //  into which we'll draw
  39. #define MAX_POLY_VERTS      8       // assumes polygons have no more than
  40.                                     //  four sides and are clipped a
  41.                                     //  maximum of four times by frustum.
  42.                                     //  Must be increased for more sides
  43.                                     //  or more clip planes
  44. #define MAX_SCREEN_HEIGHT   2048
  45. #define MOVEMENT_SPEED      3.0
  46. #define VMOVEMENT_SPEED     3.0
  47. #define MAX_MOVEMENT_SPEED  30.0
  48. #define PI                  3.141592
  49. #define ROLL_SPEED          (PI/20.0)
  50. #define PITCH_SPEED         (PI/20.0)
  51. #define YAW_SPEED           (PI/20.0)
  52. #define MAX_COORD           0x4000
  53. #define NUM_FRUSTUM_PLANES  4
  54. #define CLIP_PLANE_EPSILON  0.0001
  55. #define MAX_SPANS           10000
  56. #define MAX_SURFS           1000
  57. #define MAX_EDGES           5000
  58.  
  59.  
  60. typedef struct {
  61.     double v[3];
  62. } point_t;
  63.  
  64. typedef struct {
  65.     double   x, y;
  66. } point2D_t;
  67.  
  68. typedef struct {
  69.     int x, y;
  70.     int count;
  71.     int color;
  72. } span_t;
  73.  
  74. typedef struct {
  75.     double  distance;
  76.     point_t normal;
  77. } plane_t;
  78.  
  79. typedef struct {
  80.     int         color;
  81.     int         numverts;
  82.     point_t     verts[MAX_POLY_VERTS];
  83.     plane_t     plane;
  84. } polygon_t;
  85.  
  86. typedef struct surf_s {
  87.     struct surf_s   *pnext, *pprev;
  88.     int             color;
  89.     int             visxstart;
  90.     double          zinv00, zinvstepx, zinvstepy;
  91.     int             state;
  92. } surf_t;
  93.  
  94. typedef struct {
  95.     int         numverts;
  96.     point2D_t   verts[MAX_POLY_VERTS];
  97. } polygon2D_t;
  98.  
  99. typedef struct convexobject_s {
  100.     struct convexobject_s   *pnext;
  101.     point_t                 center;
  102.     int                     numpolys;
  103.     polygon_t               *ppoly;
  104. } convexobject_t;
  105.  
  106. typedef struct edge_s {
  107.     int             x;
  108.     int             xstep;
  109.     int             leading;
  110.     surf_t          *psurf;
  111.     struct edge_s   *pnext, *pprev;
  112.     struct edge_s   *pnextremove;
  113. } edge_t;
  114.  
  115. BITMAPINFO *pbmiDIB;        // pointer to the BITMAPINFO
  116. char *pDIB, *pDIBBase;        // pointers to DIB section we'll draw into
  117. HBITMAP hDIBSection;        // handle of DIB section
  118. HINSTANCE hInst;            // current instance
  119. char szAppName[] = "Clip";  // The name of this application
  120. char szTitle[]   = "3D clipping demo"; // The title bar text
  121. HPALETTE hpalold, hpalDIB;
  122. HWND hwndOutput;
  123. int DIBWidth, DIBHeight;
  124. int DIBPitch;
  125. double  roll, pitch, yaw;
  126. double  currentspeed;
  127. point_t currentpos;
  128. double  fieldofview, xcenter, ycenter;
  129. double  xscreenscale, yscreenscale, maxscale;
  130. double  maxscreenscaleinv;
  131. int     numobjects;
  132. double  speedscale = 1.0;
  133. plane_t frustumplanes[NUM_FRUSTUM_PLANES];
  134.  
  135. double  mroll[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  136. double  mpitch[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  137. double  myaw[3][3] =  {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
  138. point_t vpn, vright, vup;
  139. point_t xaxis = {1, 0, 0};
  140. point_t zaxis = {0, 0, 1};
  141.  
  142. polygon_t polys0[] = {
  143. {15, 4, {{-10,10,-10}, {10,10,-10}, {10,-10,-10}, {-10,-10,-10}},
  144.     {10, {0, 0, -1}}},
  145. {14, 4, {{10,10,-10}, {10,10,10}, {10,-10,10}, {10,-10,-10}},
  146.     {10, {1, 0, 0}}},
  147. {13, 4, {{10,10,10}, {-10,10,10}, {-10,-10,10}, {10,-10,10}},
  148.     {10, {0, 0, 1}}},
  149. {12, 4, {{-10,10,10}, {-10,10,-10}, {-10,-10,-10}, {-10,-10,10}},
  150.     {10, {-1, 0, 0}}},
  151. {11, 4, {{-10,10,-10}, {-10,10,10}, {10,10,10}, {10,10,-10}},
  152.     {10, {0, 1, 0}}},
  153. {10, 4, {{-10,-10,-10}, {10,-10,-10}, {10,-10,10}, {-10,-10,10}},
  154.     {10, {0, -1, 0}}},
  155. };
  156.  
  157. polygon_t polys1[] = {
  158. {1, 4, {{-200,0,-200}, {-200,0,200},
  159.         {200,0,200}, {200,0,-200}}, {0, {0, 1, 0}}},
  160. };
  161.  
  162. polygon_t polys2[] = {
  163. {6, 4, {{0,10,0}, {20,10,0}, {10,10,-10}, {0,10,-10}},
  164.     {10, {0, 1, 0}}},
  165. {6, 4, {{-10,10,10}, {0,10,10}, {0,10,0}, {-10,10,0}},
  166.     {10, {0, 1, 0}}},
  167. {6, 4, {{0,10,0}, {0,10,-10}, {-10,10,-10}, {-10,10,0}},
  168.     {10, {0, 1, 0}}},
  169. {5, 4, {{0,-10,0}, {0,-10,-10}, {10,-10,-10}, {20,-10,0}},
  170.     {10, {0, -1, 0}}},
  171. {5, 4, {{-10,-10,10}, {-10,-10,0}, {0,-10,0}, {0,-10,10}},
  172.     {10, {0, -1, 0}}},
  173. {5, 4, {{-10,-10,0}, {-10,-10,-10}, {0,-10,-10}, {0,-10,0}},
  174.     {10, {0, -1, 0}}},
  175. {4, 4, {{-10,10,-10}, {10,10,-10}, {10,-10,-10}, {-10,-10,-10}},
  176.     {10, {0, 0, -1}}},
  177. {3, 4, {{10,10,-10}, {20,10,0}, {20,-10,0}, {10,-10,-10}},
  178.     {14.14, {0.707, 0, -0.707}}},
  179. {2, 4, {{20,10,0}, {0,10,0}, {0,-10,0}, {20,-10,0}},
  180.     {0, {0, 0, 1}}},
  181. {9, 4, {{0,10,0}, {0,10,10}, {0,-10,10}, {0,-10,0}},
  182.     {0, {1, 0, 0}}},
  183. {15, 4, {{0,10,10}, {-10,10,10}, {-10,-10,10}, {0,-10,10}},
  184.     {10, {0, 0, 1}}},
  185. {14, 4, {{-10,10,10}, {-10,10,-10}, {-10,-10,-10}, {-10,-10,10}},
  186.     {10, {-1, 0, 0}}},
  187. };
  188.  
  189. extern convexobject_t   objecthead;
  190.  
  191. convexobject_t objects[] = {
  192. {&objects[1], {-50,0,70}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  193. {&objects[2], {0,20,70}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  194. {&objects[3], {50,0,70}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  195. {&objects[4], {-50,0,-70}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  196. {&objects[5], {0,20,-70}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  197. {&objects[6], {50,30,-70}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  198. {&objects[7], {-50,15,0}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  199. {&objects[8], {50,15,0}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  200. {&objects[9], {0,50,0}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  201. {&objects[10], {-100,100,115}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  202. {&objects[11], {-100,150,120}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  203. {&objects[12], {100,200,100}, sizeof(polys0) / sizeof(polys0[0]), polys0},
  204. {&objects[13], {100,100,100}, sizeof(polys2) / sizeof(polys2[0]), polys2},
  205. {&objecthead, {0,-20,0}, sizeof(polys1) / sizeof(polys1[0]), polys1},
  206. };
  207.  
  208. // Head and tail for the object list
  209. convexobject_t objecthead = {&objects[0]};
  210.  
  211. // Span, edge, and surface lists
  212. span_t  spans[MAX_SPANS];
  213. edge_t  edges[MAX_EDGES];
  214. surf_t  surfs[MAX_SURFS];
  215.  
  216. // Bucket list of new edges to add on each scan line
  217. edge_t  newedges[MAX_SCREEN_HEIGHT];
  218.  
  219. // Bucket list of edges to remove on each scan line
  220. edge_t  *removeedges[MAX_SCREEN_HEIGHT];
  221.  
  222. // Head and tail for the active edge list
  223. edge_t  edgehead;
  224. edge_t  edgetail;
  225.  
  226. // Edge used as sentinel of new edge lists
  227. edge_t  maxedge = {0x7FFFFFFF};
  228.  
  229. // Head/tail/sentinel/background surface of active surface stack
  230. surf_t  surfstack;
  231.  
  232. // pointers to next available surface and edge
  233. surf_t  *pavailsurf;
  234. edge_t  *pavailedge;
  235.  
  236. int currentcolor;
  237.  
  238. void UpdateWorld(void);
  239.  
  240. /////////////////////////////////////////////////////////////////////
  241. // WinMain
  242. /////////////////////////////////////////////////////////////////////
  243. int APIENTRY WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
  244.     LPSTR lpCmdLine, int nCmdShow)
  245. {
  246.     MSG msg;
  247.     HANDLE hAccelTable;
  248.  
  249.     if (!hPrevInstance) {       // Other instances of app running?
  250.         if (!InitApplication(hInstance)) { // Initialize shared things
  251.             return (FALSE);     // Exits if unable to initialize
  252.         }
  253.     }
  254.  
  255.     // Perform initializations that apply to a specific instance
  256.     if (!InitInstance(hInstance, nCmdShow)) {
  257.         return (FALSE);
  258.     }
  259.  
  260.     hAccelTable = LoadAccelerators (hInstance, szAppName);
  261.  
  262.     // Acquire and dispatch messages until a WM_QUIT message is
  263.     // received
  264.     for (;;) {
  265.         if (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE)) {
  266.             do {
  267.                 if (msg.message == WM_QUIT) {
  268.                     goto Done;
  269.                 }
  270.                   if (!TranslateAccelerator (msg.hwnd, hAccelTable,
  271.                           &msg)) {
  272.                     TranslateMessage(&msg);// xlates virt keycodes
  273.                        DispatchMessage(&msg); // Dispatches msg to window
  274.                       }
  275.             } while (PeekMessage(&msg, NULL, 0, 0, PM_REMOVE));
  276.         }
  277.         // Update the world
  278.         UpdateWorld();
  279.     }
  280.  
  281. Done:
  282.     return (msg.wParam); // Returns the value from PostQuitMessage
  283.  
  284.     lpCmdLine; // This will prevent 'unused formal parameter' warnings
  285. }
  286.  
  287. /////////////////////////////////////////////////////////////////////
  288. // InitApplication
  289. /////////////////////////////////////////////////////////////////////
  290. BOOL InitApplication(HINSTANCE hInstance)
  291. {
  292.         WNDCLASS  wc;
  293.  
  294.         // Fill in window class structure with parameters that
  295.         // describe the main window.
  296.         wc.style         = CS_HREDRAW | CS_VREDRAW;
  297.         wc.lpfnWndProc   = (WNDPROC)WndProc;
  298.         wc.cbClsExtra    = 0;
  299.         wc.cbWndExtra    = 0;
  300.         wc.hInstance     = hInstance;
  301.         wc.hIcon         = LoadIcon (hInstance, szAppName);
  302.         wc.hCursor       = LoadCursor(NULL, IDC_ARROW);
  303.         wc.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);
  304.         wc.lpszMenuName  = szAppName;
  305.         wc.lpszClassName = szAppName;
  306.  
  307.         // Register the window class and return success/failure code.
  308.         return (RegisterClass(&wc));
  309. }
  310.  
  311. /////////////////////////////////////////////////////////////////////
  312. // InitInstance
  313. /////////////////////////////////////////////////////////////////////
  314. BOOL InitInstance(
  315.         HINSTANCE       hInstance,
  316.         int             nCmdShow)
  317. {
  318.         HWND            hwnd; // Main window handle.
  319.         HDC                hdc;
  320.         INT                i, j, k;
  321.         LOGPALETTE *    plogpal;
  322.         PUSHORT         pusTemp;
  323.         HPALETTE        hpal;
  324.         RECT            rctmp;
  325.         int                screenx, screeny;
  326.  
  327.         // Save the instance handle in static variable, which will be
  328.         // used in many subsequent calls from this application to
  329.         // Windows
  330.         hInst = hInstance; // Store inst handle in our global variable
  331.  
  332.         // Create a main window for this application instance
  333.         DIBWidth = INITIAL_DIB_WIDTH;
  334.         DIBHeight = INITIAL_DIB_HEIGHT;
  335.            rctmp.left = 0;
  336.         rctmp.top = 0;
  337.         rctmp.right = DIBWidth;
  338.         rctmp.bottom = DIBHeight;
  339.    
  340.           AdjustWindowRect(&rctmp, WS_OVERLAPPEDWINDOW, 1);
  341.  
  342.         screenx = GetSystemMetrics(SM_CXSCREEN);
  343.         screeny = GetSystemMetrics(SM_CYSCREEN);
  344.  
  345.         hwnd = CreateWindow(
  346.                 szAppName,           // See RegisterClass() call.
  347.                 szTitle,             // Text for window title bar.
  348.                 WS_OVERLAPPEDWINDOW,// Window style.
  349.                 screenx - (rctmp.right - rctmp.left),
  350.                 screeny - (rctmp.bottom - rctmp.top),
  351.                 rctmp.right - rctmp.left,
  352.                 rctmp.bottom - rctmp.top,
  353.                 NULL,
  354.                 NULL,
  355.                 hInstance,
  356.                 NULL
  357.         );
  358.  
  359.         // If window could not be created, return "failure"
  360.         if (!hwnd) {
  361.             return (FALSE);
  362.         }
  363.  
  364.         // Make the window visible and draw it
  365.         ShowWindow(hwnd, nCmdShow); // Show the window
  366.         UpdateWindow(hwnd);         // Sends WM_PAINT message
  367.  
  368.         hdc = GetDC(hwnd);
  369.  
  370.         // For 256-color mode, set up the palette for maximum speed
  371.         // in copying to the screen. If not a 256-color mode, the
  372.         // adapter isn't palettized, so we'll just use the default
  373.         // palette. However, we will run a lot slower in this case
  374.         // due to translation while copying
  375.         if (GetDeviceCaps(hdc, RASTERCAPS) & RC_PALETTE) {
  376.             // This is a 256-color palettized mode.
  377.             // Set up and realize our palette and the identity color
  378.             // table for the DIB (identity means that DIB color
  379.             // indices and screen palette indices match exactly, so
  380.             // GDI doesn't have to do any translation when copying
  381.             // from DIB to screen. This helps performance a lot)
  382.             plogpal = malloc(sizeof(LOGPALETTE) +
  383.                     256 * sizeof(PALETTEENTRY));
  384.  
  385.             if (plogpal == NULL) {
  386.                 return(FALSE);
  387.             }
  388.  
  389.             // Take up all physical palette entries, to flush out
  390.             // anything that's currently in the palette
  391.             plogpal->palVersion = 0x300;
  392.             plogpal->palNumEntries = 236;
  393.             for (i=0; i<236; i++) {
  394.                 plogpal->palPalEntry[i].peRed = i;
  395.                 plogpal->palPalEntry[i].peGreen = 0;
  396.                 plogpal->palPalEntry[i].peBlue = 0;
  397.                 plogpal->palPalEntry[i].peFlags =
  398.                         PC_RESERVED | PC_NOCOLLAPSE;
  399.             }
  400.  
  401.             hpal = CreatePalette(plogpal);
  402.  
  403.             if (hpal == 0) {
  404.                 return(FALSE);
  405.             }
  406.  
  407.             hpalold = SelectPalette(hdc, hpal, FALSE);
  408.  
  409.             if (hpalold == 0) {
  410.                 return(FALSE);
  411.             }
  412.  
  413.             if (RealizePalette(hdc) != plogpal->palNumEntries) {
  414.                 return(FALSE);
  415.             }
  416.  
  417.             if (SelectPalette(hdc, hpalold, FALSE) == 0) {
  418.                 return(FALSE);
  419.             }
  420.  
  421.             if (!DeleteObject(hpal)) {
  422.                 return(FALSE);
  423.             }
  424.  
  425.             // Now set up the 6value-6value-6value RGB palette,
  426.             // followed by 20 gray levels, that we want to work with
  427.             // into the physical palette
  428.             for (i=0; i<6; i++) {
  429.                 for (j=0; j<6; j++) {
  430.                     for (k=0; k<6; k++) {
  431.                         plogpal->palPalEntry[i*36+j*6+k].peRed =
  432.                                 i*255/6;
  433.                         plogpal->palPalEntry[i*36+j*6+k].peGreen =
  434.                                 j*255/6;
  435.                         plogpal->palPalEntry[i*36+j*6+k].peBlue =
  436.                                    k*255/6;
  437.                         plogpal->palPalEntry[i*36+j*6+k].peFlags =
  438.                             PC_RESERVED | PC_NOCOLLAPSE;
  439.                     }
  440.                 }
  441.             }
  442.  
  443.             for (i=0; i<20; i++) {
  444.                 plogpal->palPalEntry[i+216].peRed = i*255/20;
  445.                 plogpal->palPalEntry[i+216].peGreen = i*255/20;
  446.                 plogpal->palPalEntry[i+216].peBlue = i*255/20;
  447.                 plogpal->palPalEntry[i+216].peFlags =
  448.                         PC_RESERVED | PC_NOCOLLAPSE;
  449.             }
  450.  
  451.             hpal = CreatePalette(plogpal);
  452.  
  453.             if (hpal == 0) {
  454.                 return(FALSE);
  455.             }
  456.  
  457.             if (SelectPalette(hdc, hpal, FALSE) == 0) {
  458.                 return(FALSE);
  459.             }
  460.  
  461.             if (RealizePalette(hdc) != plogpal->palNumEntries) {
  462.                 return(FALSE);
  463.             }
  464.  
  465.             // Get back the 256 colors now in the physical palette,
  466.             // which are the 236 we just selected, plus the 20 static
  467.             // colors
  468.             if (GetSystemPaletteEntries(hdc, 0, 256,
  469.                     plogpal->palPalEntry) != 256) {
  470.                 return(FALSE);
  471.             }
  472.  
  473.             for (i=10; i<246; i++) {
  474.                 plogpal->palPalEntry[i].peFlags =
  475.                         PC_RESERVED | PC_NOCOLLAPSE;
  476.             }
  477.  
  478.             // Now create a logical palette that exactly matches the
  479.             // physical palette, and realize it. This is the palette
  480.             // into which the DIB pixel values will be indices
  481.             plogpal->palNumEntries = 256;
  482.  
  483.             hpalDIB = CreatePalette(plogpal);
  484.  
  485.             if (hpalDIB == 0)
  486.                 return(FALSE);
  487.  
  488.             if (SelectPalette(hdc, hpalDIB, FALSE) == 0)
  489.                 return(FALSE);
  490.  
  491.             DeleteObject(hpal);
  492.  
  493.             if (RealizePalette(hdc) != plogpal->palNumEntries)
  494.                 return(FALSE);
  495.  
  496.             if (SelectPalette(hdc, hpalold, FALSE) == FALSE)
  497.                 return(FALSE);
  498.  
  499.                free(plogpal);
  500.         }
  501.  
  502.         // Finally, set up the DIB section
  503.         pbmiDIB = malloc(sizeof(BITMAPINFO) - 4 + 256*sizeof(USHORT));
  504.  
  505.         if (pbmiDIB == NULL)
  506.             return(FALSE);
  507.  
  508.  
  509.         pbmiDIB->bmiHeader.biSize = sizeof(BITMAPINFOHEADER);
  510.         pbmiDIB->bmiHeader.biWidth = DIBWidth;
  511.         pbmiDIB->bmiHeader.biHeight = DIBHeight;
  512.         pbmiDIB->bmiHeader.biPlanes = 1;
  513.         pbmiDIB->bmiHeader.biBitCount = 8;
  514.         pbmiDIB->bmiHeader.biCompression = BI_RGB;
  515.         pbmiDIB->bmiHeader.biSizeImage = 0;
  516.         pbmiDIB->bmiHeader.biXPelsPerMeter = 0;
  517.         pbmiDIB->bmiHeader.biYPelsPerMeter = 0;
  518.         pbmiDIB->bmiHeader.biClrUsed = 256;
  519.         pbmiDIB->bmiHeader.biClrImportant = 256;
  520.  
  521.         pusTemp = (PUSHORT) pbmiDIB->bmiColors;
  522.  
  523.         for (i=0; i<256; i++) {
  524.             *pusTemp++ = i;
  525.         }
  526.  
  527.         hDIBSection = CreateDIBSection (hdc, pbmiDIB, DIB_PAL_COLORS,
  528.                           &pDIBBase, NULL, 0);
  529.  
  530.         if (!hDIBSection) {
  531.             free(pbmiDIB);
  532.             return(FALSE);
  533.         }
  534.  
  535.         if (pbmiDIB->bmiHeader.biHeight > 0)
  536.         {
  537.             pDIB = (pDIBBase + (DIBHeight - 1) * DIBWidth);
  538.             DIBPitch = -DIBWidth;   // bottom-up
  539.         }
  540.         else
  541.         {
  542.             pDIB = pDIBBase;
  543.             DIBPitch = DIBWidth;    // top-down
  544.         }
  545.  
  546.         // Clear the DIB
  547.         memset(pDIBBase, 0, DIBWidth*DIBHeight);
  548.  
  549.         ReleaseDC(hwnd, hdc);
  550.  
  551.         hwndOutput = hwnd;
  552.  
  553.         // Set the initial location, direction, and speed
  554.         roll = 0.0;
  555.         pitch = 0.0;
  556.         yaw = 0.0;
  557.         currentspeed = 0.0;
  558.         currentpos.v[0] = 0.0;
  559.         currentpos.v[1] = 0.0;
  560.         currentpos.v[2] = 0.0;
  561.         fieldofview = 2.0;
  562.         xscreenscale = DIBWidth / fieldofview;
  563.         yscreenscale = DIBHeight / fieldofview;
  564.         maxscale = max(xscreenscale, yscreenscale);
  565.         maxscreenscaleinv = 1.0 / maxscale;
  566.         xcenter = DIBWidth / 2.0 - 0.5;
  567.         ycenter = DIBHeight / 2.0 - 0.5;
  568.  
  569.         numobjects = sizeof(objects) / sizeof(objects[0]);
  570.  
  571.         return (TRUE);              // We succeeded...
  572. }
  573.  
  574. /////////////////////////////////////////////////////////////////////
  575. // WndProc
  576. /////////////////////////////////////////////////////////////////////
  577. LRESULT CALLBACK WndProc(
  578.                 HWND hwnd,         // window handle
  579.                 UINT message,      // type of message
  580.                 WPARAM uParam,     // additional information
  581.                 LPARAM lParam)     // additional information
  582. {
  583.     int wmId, wmEvent;
  584.     UINT fwSizeType;
  585.     int oldDIBWidth, oldDIBHeight;
  586.     HBITMAP holdDIBSection;
  587.     HDC hdc;
  588.  
  589.     switch (message) {
  590.  
  591.     case WM_COMMAND:  // message: command from application menu
  592.  
  593.         wmId    = LOWORD(uParam);
  594.         wmEvent = HIWORD(uParam);
  595.  
  596.         switch (wmId) {
  597.  
  598.          case IDM_EXIT:
  599.             DestroyWindow (hwnd);
  600.             break;
  601.  
  602.         default:
  603.             return (DefWindowProc(hwnd, message, uParam, lParam));
  604.         }
  605.         break;
  606.  
  607.     case WM_KEYDOWN:
  608.         switch (uParam) {
  609.  
  610.         case VK_DOWN:
  611.             currentspeed -= MOVEMENT_SPEED * speedscale;
  612.             if (currentspeed < -(MAX_MOVEMENT_SPEED * speedscale))
  613.                 currentspeed = -(MAX_MOVEMENT_SPEED * speedscale);
  614.             break;
  615.  
  616.         case VK_UP:
  617.             currentspeed += MOVEMENT_SPEED * speedscale;
  618.             if (currentspeed > (MAX_MOVEMENT_SPEED * speedscale))
  619.                 currentspeed = (MAX_MOVEMENT_SPEED * speedscale);
  620.             break;
  621.  
  622.         case 'N':
  623.             roll += ROLL_SPEED * speedscale;
  624.             if (roll >= (PI * 2))
  625.                 roll -= PI * 2;
  626.             break;
  627.  
  628.         case 'M':
  629.             roll -= ROLL_SPEED * speedscale;
  630.             if (roll < 0)
  631.                 roll += PI * 2;
  632.             break;
  633.  
  634.         case 'A':
  635.             pitch -= PITCH_SPEED * speedscale;
  636.             if (pitch < 0)
  637.                 pitch += PI * 2;
  638.             break;
  639.  
  640.         case 'Z':
  641.             pitch += PITCH_SPEED * speedscale;
  642.             if (pitch >= (PI * 2))
  643.                 pitch -= PI * 2;
  644.             break;
  645.  
  646.         case 'D':
  647.             currentpos.v[1] += VMOVEMENT_SPEED;
  648.             break;
  649.  
  650.         case 'C':
  651.             currentpos.v[1] -= VMOVEMENT_SPEED;
  652.             break;
  653.  
  654.         case VK_LEFT:
  655.             yaw -= YAW_SPEED * speedscale;
  656.             if (yaw < 0)
  657.                 yaw += PI * 2;
  658.             break;
  659.  
  660.         case VK_RIGHT:
  661.             yaw += YAW_SPEED * speedscale;
  662.             if (yaw >= (PI * 2))
  663.                 yaw -= PI * 2;
  664.             break;
  665.  
  666.         default:
  667.             break;
  668.         }
  669.         return(0);
  670.  
  671.     case WM_KEYUP:
  672.         switch (uParam) {
  673.  
  674.         case VK_SUBTRACT:
  675.             fieldofview *= 0.9;
  676.             xscreenscale = DIBWidth / fieldofview;
  677.             yscreenscale = DIBHeight / fieldofview;
  678.             maxscale = max(xscreenscale, yscreenscale);
  679.             break;
  680.  
  681.         case VK_ADD:
  682.             fieldofview *= 1.1;
  683.             xscreenscale = DIBWidth / fieldofview;
  684.             yscreenscale = DIBHeight / fieldofview;
  685.             maxscale = max(xscreenscale, yscreenscale);
  686.             break;
  687.  
  688.         case 'F':
  689.             speedscale *= 1.1;
  690.             break;
  691.  
  692.         case 'S':
  693.             speedscale *= 0.9;
  694.             break;
  695.  
  696.         default:
  697.             break;
  698.         }
  699.         return(0);
  700.  
  701.     case WM_SIZE:    // window size changed
  702.         fwSizeType = uParam;
  703.         if (fwSizeType != SIZE_MINIMIZED) {
  704.             // Skip when this is called before the first DIB
  705.             // section is created
  706.             if (hDIBSection == 0)
  707.                 break;
  708.  
  709.             oldDIBWidth = DIBWidth;
  710.             oldDIBHeight = DIBHeight;
  711.  
  712.             DIBWidth = LOWORD(lParam);
  713.             DIBWidth = (DIBWidth + 3) & ~3;
  714.             DIBHeight = HIWORD(lParam);
  715.  
  716.             if ((DIBHeight < 10) || (DIBWidth < 10))
  717.             {
  718.             // Keep the DIB section big enough so we don't start
  719.             // drawing outside the DIB (the window can get smaller,
  720.             // but we don't really care, and GDI will clip the
  721.             // blts for us)
  722.                 DIBWidth = oldDIBWidth;
  723.                 DIBHeight = oldDIBHeight;
  724.             }
  725.  
  726.             // Resize the DIB section to the new size
  727.             holdDIBSection = hDIBSection;
  728.             pbmiDIB->bmiHeader.biWidth = DIBWidth;
  729.             pbmiDIB->bmiHeader.biHeight = DIBHeight;
  730.  
  731.             hdc = GetDC(hwnd);
  732.             hDIBSection = CreateDIBSection (hdc, pbmiDIB,
  733.                     DIB_PAL_COLORS, &pDIBBase, NULL, 0);
  734.  
  735.             if (hDIBSection) {
  736.                 // Success
  737.                 DeleteObject(holdDIBSection);
  738.  
  739.                 if (pbmiDIB->bmiHeader.biHeight > 0)
  740.                 {
  741.                     pDIB = (pDIBBase + (DIBHeight - 1) * DIBWidth);
  742.                     DIBPitch = -DIBWidth;   // bottom-up
  743.                 }
  744.                 else
  745.                 {
  746.                     pDIB = pDIBBase;
  747.                     DIBPitch = DIBWidth;    // top-down
  748.                 }
  749.  
  750.                 xscreenscale = DIBWidth / fieldofview;
  751.                 yscreenscale = DIBHeight / fieldofview;
  752.                 maxscale = max(xscreenscale, yscreenscale);
  753.                 xcenter = DIBWidth / 2.0 - 0.5;
  754.                 ycenter = DIBHeight / 2.0 - 0.5;
  755.             } else {
  756.                 // Failed, just use old size
  757.                 pbmiDIB->bmiHeader.biWidth = oldDIBWidth;
  758.                 pbmiDIB->bmiHeader.biHeight = oldDIBHeight;
  759.                 DIBWidth = oldDIBWidth;
  760.                 DIBHeight = oldDIBHeight;
  761.             }
  762.  
  763.             // Clear the DIB
  764.             memset(pDIBBase, 0, DIBWidth*DIBHeight);
  765.         }
  766.         break;
  767.  
  768.     case WM_DESTROY:  // message: window being destroyed
  769.         free(pbmiDIB);
  770.         DeleteObject(hDIBSection);
  771.         DeleteObject(hpalold);
  772.                         
  773.         PostQuitMessage(0);
  774.         break;
  775.  
  776.     default:          // Passes it on if unproccessed
  777.         return (DefWindowProc(hwnd, message, uParam, lParam));
  778.     }
  779.     return (0);
  780. }
  781.  
  782. /////////////////////////////////////////////////////////////////////
  783. // 3-D dot product.
  784. /////////////////////////////////////////////////////////////////////
  785. double DotProduct(point_t *vec1, point_t *vec2)
  786. {
  787.     return vec1->v[0] * vec2->v[0] +
  788.            vec1->v[1] * vec2->v[1] +
  789.            vec1->v[2] * vec2->v[2];
  790. }
  791.  
  792. /////////////////////////////////////////////////////////////////////
  793. // 3-D cross product.
  794. /////////////////////////////////////////////////////////////////////
  795. void CrossProduct(point_t *in1, point_t *in2, point_t *out)
  796. {
  797.     out->v[0] = in1->v[1] * in2->v[2] - in1->v[2] * in2->v[1];
  798.     out->v[1] = in1->v[2] * in2->v[0] - in1->v[0] * in2->v[2];
  799.     out->v[2] = in1->v[0] * in2->v[1] - in1->v[1] * in2->v[0];
  800. }
  801.  
  802. /////////////////////////////////////////////////////////////////////
  803. // Concatenate two 3x3 matrices.
  804. /////////////////////////////////////////////////////////////////////
  805. void MConcat(double in1[3][3], double in2[3][3], double out[3][3])
  806. {
  807.     int     i, j;
  808.  
  809.     for (i=0 ; i<3 ; i++)
  810.     {
  811.         for (j=0 ; j<3 ; j++)
  812.         {
  813.             out[i][j] = in1[i][0] * in2[0][j] +
  814.                         in1[i][1] * in2[1][j] +
  815.                         in1[i][2] * in2[2][j];
  816.         }
  817.     }
  818. }
  819.  
  820. /////////////////////////////////////////////////////////////////////
  821. // Project viewspace polygon vertices into screen coordinates.
  822. // Note that the y axis goes up in worldspace and viewspace, but
  823. // goes down in screenspace.
  824. /////////////////////////////////////////////////////////////////////
  825. void ProjectPolygon (polygon_t *ppoly, polygon2D_t *ppoly2D)
  826. {
  827.     int     i;
  828.     double  zrecip;
  829.  
  830.     for (i=0 ; i<ppoly->numverts ; i++)
  831.     {
  832.         zrecip = 1.0 / ppoly->verts[i].v[2];
  833.         ppoly2D->verts[i].x =
  834.                 ppoly->verts[i].v[0] * zrecip * maxscale + xcenter;
  835.         ppoly2D->verts[i].y = ycenter -
  836.                 (ppoly->verts[i].v[1] * zrecip * maxscale);
  837.     }
  838.  
  839.     ppoly2D->numverts = ppoly->numverts;
  840. }
  841.  
  842. /////////////////////////////////////////////////////////////////////
  843. // Move the view position and set the world->view transform.
  844. /////////////////////////////////////////////////////////////////////
  845. void UpdateViewPos()
  846. {
  847.     int     i;
  848.     point_t motionvec;
  849.     double  s, c, mtemp1[3][3], mtemp2[3][3];
  850.  
  851.     // Move in the view direction, across the x-y plane, as if
  852.     // walking. This approach moves slower when looking up or
  853.     // down at more of an angle
  854.     motionvec.v[0] = DotProduct(&vpn, &xaxis);
  855.     motionvec.v[1] = 0.0;
  856.     motionvec.v[2] = DotProduct(&vpn, &zaxis);
  857.  
  858.     for (i=0 ; i<3 ; i++)
  859.     {
  860.         currentpos.v[i] += motionvec.v[i] * currentspeed;
  861.         if (currentpos.v[i] > MAX_COORD)
  862.             currentpos.v[i] = MAX_COORD;
  863.         if (currentpos.v[i] < -MAX_COORD)
  864.             currentpos.v[i] = -MAX_COORD;
  865.     }
  866.  
  867.     // Set up the world-to-view rotation.
  868.     // Note: much of the work done in concatenating these matrices
  869.     // can be factored out, since it contributes nothing to the
  870.     // final result; multiply the three matrices together on paper
  871.     // to generate a minimum equation for each of the 9 final elements
  872.     s = sin(roll);
  873.     c = cos(roll);
  874.     mroll[0][0] = c;
  875.     mroll[0][1] = s;
  876.     mroll[1][0] = -s;
  877.     mroll[1][1] = c;
  878.  
  879.     s = sin(pitch);
  880.     c = cos(pitch);
  881.     mpitch[1][1] = c;
  882.     mpitch[1][2] = s;
  883.     mpitch[2][1] = -s;
  884.     mpitch[2][2] = c;
  885.  
  886.     s = sin(yaw);
  887.     c = cos(yaw);
  888.     myaw[0][0] = c;
  889.     myaw[0][2] = -s;
  890.     myaw[2][0] = s;
  891.     myaw[2][2] = c;
  892.  
  893.     MConcat(mroll, myaw, mtemp1);
  894.     MConcat(mpitch, mtemp1, mtemp2);
  895.  
  896.     // Break out the rotation matrix into vright, vup, and vpn.
  897.     // We could work directly with the matrix; breaking it out
  898.     // into three vectors is just to make things clearer
  899.     for (i=0 ; i<3 ; i++)
  900.     {
  901.         vright.v[i] = mtemp2[0][i];
  902.         vup.v[i] = mtemp2[1][i];
  903.         vpn.v[i] = mtemp2[2][i];
  904.     }
  905.  
  906.     // Simulate crude friction
  907.     if (currentspeed > (MOVEMENT_SPEED * speedscale / 2.0))
  908.         currentspeed -= MOVEMENT_SPEED * speedscale / 2.0;
  909.     else if (currentspeed < -(MOVEMENT_SPEED * speedscale / 2.0))
  910.         currentspeed += MOVEMENT_SPEED * speedscale / 2.0;
  911.     else
  912.         currentspeed = 0.0;
  913. }
  914.  
  915. /////////////////////////////////////////////////////////////////////
  916. // Rotate a vector from viewspace to worldspace.
  917. /////////////////////////////////////////////////////////////////////
  918. void BackRotateVector(point_t *pin, point_t *pout)
  919. {
  920.     int     i;
  921.  
  922.     // Rotate into the world orientation
  923.     for (i=0 ; i<3 ; i++)
  924.     {
  925.         pout->v[i] = pin->v[0] * vright.v[i] +
  926.                      pin->v[1] * vup.v[i] +
  927.                      pin->v[2] * vpn.v[i];
  928.     }
  929. }
  930.  
  931. /////////////////////////////////////////////////////////////////////
  932. // Transform a point from worldspace to viewspace.
  933. /////////////////////////////////////////////////////////////////////
  934. void TransformPoint(point_t *pin, point_t *pout)
  935. {
  936.     int     i;
  937.     point_t tvert;
  938.  
  939.     // Translate into a viewpoint-relative coordinate
  940.     for (i=0 ; i<3 ; i++)
  941.     {
  942.         tvert.v[i] = pin->v[i] - currentpos.v[i];
  943.     }
  944.  
  945.     // Rotate into the view orientation
  946.     pout->v[0] = DotProduct(&tvert, &vright);
  947.     pout->v[1] = DotProduct(&tvert, &vup);
  948.     pout->v[2] = DotProduct(&tvert, &vpn);
  949. }
  950.  
  951. /////////////////////////////////////////////////////////////////////
  952. // Transform a polygon from worldspace to viewspace.
  953. /////////////////////////////////////////////////////////////////////
  954. void TransformPolygon(polygon_t *pinpoly, polygon_t *poutpoly)
  955. {
  956.     int     i;
  957.  
  958.     for (i=0 ; i<pinpoly->numverts ; i++)
  959.     {
  960.         TransformPoint(&pinpoly->verts[i], &poutpoly->verts[i]);
  961.     }
  962.  
  963.     poutpoly->numverts = pinpoly->numverts;
  964. }
  965.  
  966. /////////////////////////////////////////////////////////////////////
  967. // Returns true if polygon faces the viewpoint, assuming a clockwise
  968. // winding of vertices as seen from the front.
  969. /////////////////////////////////////////////////////////////////////
  970. int PolyFacesViewer(polygon_t *ppoly, plane_t *pplane)
  971. {
  972.     int     i;
  973.     point_t viewvec;
  974.  
  975.     for (i=0 ; i<3 ; i++)
  976.     {
  977.         viewvec.v[i] = ppoly->verts[0].v[i] - currentpos.v[i];
  978.     }
  979.  
  980.     // Use an epsilon here so we don't get polygons tilted so
  981.     // sharply that the gradients are unusable or invalid
  982.     if (DotProduct (&viewvec, &pplane->normal) < -0.01)
  983.         return 1;
  984.     else
  985.         return 0;
  986. }
  987.  
  988. /////////////////////////////////////////////////////////////////////
  989. // Set up a clip plane with the specified normal.
  990. /////////////////////////////////////////////////////////////////////
  991. void SetWorldspaceClipPlane(point_t *normal, plane_t *plane)
  992. {
  993.  
  994.     // Rotate the plane normal into worldspace
  995.     BackRotateVector(normal, &plane->normal);
  996.  
  997.     plane->distance = DotProduct(¤tpos, &plane->normal) +
  998.             CLIP_PLANE_EPSILON;
  999. }
  1000.  
  1001. /////////////////////////////////////////////////////////////////////
  1002. // Set up the planes of the frustum, in worldspace coordinates.
  1003. /////////////////////////////////////////////////////////////////////
  1004. void SetUpFrustum(void)
  1005. {
  1006.     double  angle, s, c;
  1007.     point_t normal;
  1008.  
  1009.     angle = atan(2.0 / fieldofview * maxscale / xscreenscale);
  1010.     s = sin(angle);
  1011.     c = cos(angle);
  1012.  
  1013.     // Left clip plane
  1014.     normal.v[0] = s;
  1015.     normal.v[1] = 0;
  1016.     normal.v[2] = c;
  1017.     SetWorldspaceClipPlane(&normal, &frustumplanes[0]);
  1018.  
  1019.     // Right clip plane
  1020.     normal.v[0] = -s;
  1021.     SetWorldspaceClipPlane(&normal, &frustumplanes[1]);
  1022.  
  1023.     angle = atan(2.0 / fieldofview * maxscale / yscreenscale);
  1024.     s = sin(angle);
  1025.     c = cos(angle);
  1026.  
  1027.     // Bottom clip plane
  1028.     normal.v[0] = 0;
  1029.     normal.v[1] = s;
  1030.     normal.v[2] = c;
  1031.     SetWorldspaceClipPlane(&normal, &frustumplanes[2]);
  1032.  
  1033.     // Top clip plane
  1034.     normal.v[1] = -s;
  1035.     SetWorldspaceClipPlane(&normal, &frustumplanes[3]);
  1036. }
  1037.  
  1038. /////////////////////////////////////////////////////////////////////
  1039. // Clip a polygon to a plane.
  1040. /////////////////////////////////////////////////////////////////////
  1041. int ClipToPlane(polygon_t *pin, plane_t *pplane, polygon_t *pout)
  1042. {
  1043.     int     i, j, nextvert, curin, nextin;
  1044.     double  curdot, nextdot, scale;
  1045.     point_t *pinvert, *poutvert;
  1046.  
  1047.     pinvert = pin->verts;
  1048.     poutvert = pout->verts;
  1049.  
  1050.     curdot = DotProduct(pinvert, &pplane->normal);
  1051.     curin = (curdot >= pplane->distance);
  1052.  
  1053.     for (i=0 ; i<pin->numverts ; i++)
  1054.     {
  1055.         nextvert = (i + 1) % pin->numverts;
  1056.  
  1057.         // Keep the current vertex if it's inside the plane
  1058.         if (curin)
  1059.             *poutvert++ = *pinvert;
  1060.  
  1061.         nextdot = DotProduct(&pin->verts[nextvert], &pplane->normal);
  1062.         nextin = (nextdot >= pplane->distance);
  1063.  
  1064.         // Add a clipped vertex if one end of the current edge is
  1065.         // inside the plane and the other is outside
  1066.         if (curin != nextin)
  1067.         {
  1068.             scale = (pplane->distance - curdot) /
  1069.                     (nextdot - curdot);
  1070.             for (j=0 ; j<3 ; j++)
  1071.             {
  1072.                 poutvert->v[j] = pinvert->v[j] +
  1073.                     ((pin->verts[nextvert].v[j] - pinvert->v[j]) *
  1074.                      scale);
  1075.             }
  1076.             poutvert++;
  1077.         }
  1078.  
  1079.         curdot = nextdot;
  1080.         curin = nextin;
  1081.         pinvert++;
  1082.     }
  1083.  
  1084.     pout->numverts = poutvert - pout->verts;
  1085.     if (pout->numverts < 3)
  1086.         return 0;
  1087.  
  1088.     return 1;
  1089. }
  1090.  
  1091. /////////////////////////////////////////////////////////////////////
  1092. // Clip a polygon to the frustum.
  1093. /////////////////////////////////////////////////////////////////////
  1094. int ClipToFrustum(polygon_t *pin, polygon_t *pout)
  1095. {
  1096.     int         i, curpoly;
  1097.     polygon_t   tpoly[2], *ppoly;
  1098.  
  1099.     curpoly = 0;
  1100.     ppoly = pin;
  1101.  
  1102.     for (i=0 ; i<(NUM_FRUSTUM_PLANES-1); i++)
  1103.     {
  1104.         if (!ClipToPlane(ppoly,
  1105.                          &frustumplanes[i],
  1106.                          &tpoly[curpoly]))
  1107.         {
  1108.             return 0;
  1109.         }
  1110.         ppoly = &tpoly[curpoly];
  1111.         curpoly ^= 1;
  1112.     }
  1113.  
  1114.     return ClipToPlane(ppoly,
  1115.                        &frustumplanes[NUM_FRUSTUM_PLANES-1],
  1116.                        pout);
  1117. }
  1118.  
  1119. /////////////////////////////////////////////////////////////////////
  1120. // Add the polygon's edges to the global edge table.
  1121. /////////////////////////////////////////////////////////////////////
  1122. void AddPolygonEdges (plane_t *plane, polygon2D_t *screenpoly)
  1123. {
  1124.     double  distinv, deltax, deltay, slope;
  1125.     int     i, nextvert, numverts, temp, topy, bottomy, height;
  1126.     edge_t  *pedge;
  1127.  
  1128.     numverts = screenpoly->numverts;
  1129.  
  1130.     // Clamp the polygon's vertices just in case some very near
  1131.     // points have wandered out of range due to floating-point
  1132.     // imprecision
  1133.     for (i=0 ; i<numverts ; i++)
  1134.     {
  1135.         if (screenpoly->verts[i].x < -0.5)
  1136.             screenpoly->verts[i].x = -0.5;
  1137.         if (screenpoly->verts[i].x > ((double)DIBWidth - 0.5))
  1138.             screenpoly->verts[i].x = (double)DIBWidth - 0.5;
  1139.         if (screenpoly->verts[i].y < -0.5)
  1140.             screenpoly->verts[i].y = -0.5;
  1141.         if (screenpoly->verts[i].y > ((double)DIBHeight - 0.5))
  1142.             screenpoly->verts[i].y = (double)DIBHeight - 0.5;
  1143.                 }
  1144.  
  1145.     // Add each edge in turn
  1146.     for (i=0 ; i<numverts ; i++)
  1147.     {
  1148.         nextvert = i + 1;
  1149.         if (nextvert >= numverts)
  1150.             nextvert = 0;
  1151.  
  1152.         topy = (int)ceil(screenpoly->verts[i].y);
  1153.         bottomy = (int)ceil(screenpoly->verts[nextvert].y);
  1154.         height = bottomy - topy;
  1155.         if (height == 0)
  1156.             continue;       // doesn't cross any scan lines
  1157.         if (height < 0)
  1158.         {
  1159.             // Leading edge
  1160.             temp = topy;
  1161.             topy = bottomy;
  1162.             bottomy = temp;
  1163.  
  1164.             pavailedge->leading = 1;
  1165.  
  1166.             deltax = screenpoly->verts[i].x -
  1167.                      screenpoly->verts[nextvert].x;
  1168.             deltay = screenpoly->verts[i].y -
  1169.                      screenpoly->verts[nextvert].y;
  1170.             slope = deltax / deltay;
  1171.  
  1172.             // Edge coordinates are in 16.16 fixed point
  1173.             pavailedge->xstep = (int)(slope * (float)0x10000);
  1174.             pavailedge->x = (int)((screenpoly->verts[nextvert].x +
  1175.                 ((float)topy - screenpoly->verts[nextvert].y) *
  1176.                 slope) * (float)0x10000);
  1177.         }
  1178.         else
  1179.         {
  1180.             // Trailing edge
  1181.             pavailedge->leading = 0;
  1182.  
  1183.             deltax = screenpoly->verts[nextvert].x -
  1184.                      screenpoly->verts[i].x;
  1185.             deltay = screenpoly->verts[nextvert].y -
  1186.                      screenpoly->verts[i].y;
  1187.             slope = deltax / deltay;
  1188.  
  1189.             // Edge coordinates are in 16.16 fixed point
  1190.             pavailedge->xstep = (int)(slope * (float)0x10000);
  1191.             pavailedge->x = (int)((screenpoly->verts[i].x +
  1192.                 ((float)topy - screenpoly->verts[i].y) * slope) *
  1193.                 (float)0x10000);
  1194.         }
  1195.  
  1196.         // Put the edge on the list to be added on top scan
  1197.         pedge = &newedges[topy];
  1198.         while (pedge->pnext->x < pavailedge->x)
  1199.             pedge = pedge->pnext;
  1200.         pavailedge->pnext = pedge->pnext;
  1201.         pedge->pnext = pavailedge;
  1202.  
  1203.         // Put the edge on the list to be removed after final scan
  1204.         pavailedge->pnextremove = removeedges[bottomy - 1];
  1205.         removeedges[bottomy - 1] = pavailedge;
  1206.  
  1207.         // Associate the edge with the surface we'll create for
  1208.         // this polygon
  1209.         pavailedge->psurf = pavailsurf;
  1210.  
  1211.         // Make sure we don't overflow the edge array
  1212.         if (pavailedge < &edges[MAX_EDGES])
  1213.             pavailedge++;
  1214.     }
  1215.  
  1216.     // Create the surface, so we'll know how to sort and draw from
  1217.     // the edges
  1218.     pavailsurf->state = 0;
  1219.     pavailsurf->color = currentcolor;
  1220.  
  1221.     // Set up the 1/z gradients from the polygon, calculating the
  1222.     // base value at screen coordinate 0,0 so we can use screen
  1223.     // coordinates directly when calculating 1/z from the gradients
  1224.     distinv = 1.0 / plane->distance;
  1225.     pavailsurf->zinvstepx = plane->normal.v[0] * distinv *
  1226.             maxscreenscaleinv * (fieldofview / 2.0);
  1227.     pavailsurf->zinvstepy = -plane->normal.v[1] * distinv *
  1228.             maxscreenscaleinv * (fieldofview / 2.0);
  1229.     pavailsurf->zinv00 = plane->normal.v[2] * distinv -
  1230.             xcenter * pavailsurf->zinvstepx -
  1231.             ycenter * pavailsurf->zinvstepy;
  1232.  
  1233.     // Make sure we don't overflow the surface array
  1234.     if (pavailsurf < &surfs[MAX_SURFS])
  1235.         pavailsurf++;
  1236. }
  1237.  
  1238. /////////////////////////////////////////////////////////////////////
  1239. // Scan all the edges in the global edge table into spans.
  1240. /////////////////////////////////////////////////////////////////////
  1241. void ScanEdges (void)
  1242. {
  1243.     int     x, y;
  1244.     double  fx, fy, zinv, zinv2;
  1245.     edge_t  *pedge, *pedge2, *ptemp;
  1246.     span_t  *pspan;
  1247.     surf_t  *psurf, *psurf2;
  1248.  
  1249.     pspan = spans;
  1250.  
  1251.     // Set up the active edge list as initially empty, containing
  1252.     // only the sentinels (which are also the background fill). Most
  1253.     // of these fields could be set up just once at start-up
  1254.     edgehead.pnext = &edgetail;
  1255.     edgehead.pprev = NULL;
  1256.     edgehead.x = -0xFFFF;           // left edge of screen
  1257.     edgehead.leading = 1;
  1258.     edgehead.psurf = &surfstack;
  1259.  
  1260.     edgetail.pnext = NULL;          // mark edge of list
  1261.     edgetail.pprev = &edgehead;
  1262.     edgetail.x = DIBWidth << 16;    // right edge of screen
  1263.     edgetail.leading = 0;
  1264.     edgetail.psurf = &surfstack;
  1265.  
  1266.     // The background surface is the entire stack initially, and
  1267.     // is infinitely far away, so everything sorts in front of it.
  1268.     // This could be set just once at start-up
  1269.     surfstack.pnext = surfstack.pprev = &surfstack;
  1270.     surfstack.color = 0;
  1271.     surfstack.zinv00 = -999999.0;
  1272.     surfstack.zinvstepx = surfstack.zinvstepy = 0.0;
  1273.  
  1274.     for (y=0 ; y<DIBHeight ; y++)
  1275.     {
  1276.         fy = (double)y;
  1277.  
  1278.         // Sort in any edges that start on this scan
  1279.         pedge = newedges[y].pnext;
  1280.         pedge2 = &edgehead;
  1281.         while (pedge != &maxedge)
  1282.         {
  1283.             while (pedge->x > pedge2->pnext->x)
  1284.                 pedge2 = pedge2->pnext;
  1285.  
  1286.             ptemp = pedge->pnext;
  1287.             pedge->pnext = pedge2->pnext;
  1288.             pedge->pprev = pedge2;
  1289.             pedge2->pnext->pprev = pedge;
  1290.             pedge2->pnext = pedge;
  1291.  
  1292.             pedge2 = pedge;
  1293.             pedge = ptemp;
  1294.         }
  1295.  
  1296.         // Scan out the active edges into spans
  1297.  
  1298.         // Start out with the left background edge already inserted,
  1299.         // and the surface stack containing only the background
  1300.         surfstack.state = 1;
  1301.         surfstack.visxstart = 0;
  1302.  
  1303.         for (pedge=edgehead.pnext ; pedge ; pedge=pedge->pnext)
  1304.         {
  1305.             psurf = pedge->psurf;
  1306.  
  1307.             if (pedge->leading)
  1308.             {
  1309.                 // It's a leading edge. Figure out where it is
  1310.                 // relative to the current surfaces and insert in
  1311.                 // the surface stack; if it's on top, emit the span
  1312.                 // for the current top.
  1313.                 // First, make sure the edges don't cross
  1314.                 if (++psurf->state == 1)
  1315.                 {
  1316.                     fx = (double)pedge->x * (1.0 / (double)0x10000);
  1317.                     // Calculate the surface's 1/z value at this pixel
  1318.                     zinv = psurf->zinv00 + psurf->zinvstepx * fx +
  1319.                             psurf->zinvstepy * fy;
  1320.  
  1321.                     // See if that makes it a new top surface
  1322.                     psurf2 = surfstack.pnext;
  1323.                     zinv2 = psurf2->zinv00 + psurf2->zinvstepx * fx +
  1324.                             psurf2->zinvstepy * fy;
  1325.                     if (zinv >= zinv2)
  1326.                     {
  1327.                         // It's a new top surface
  1328.                         // emit the span for the current top
  1329.                         x = (pedge->x + 0xFFFF) >> 16;
  1330.                         pspan->count = x - psurf2->visxstart;
  1331.                         if (pspan->count > 0)
  1332.                         {
  1333.                             pspan->y = y;
  1334.                             pspan->x = psurf2->visxstart;
  1335.                             pspan->color = psurf2->color;
  1336.  
  1337.                             // Make sure we don't overflow
  1338.                             // the span array
  1339.                             if (pspan < &spans[MAX_SPANS])
  1340.                                 pspan++;
  1341.                         }
  1342.  
  1343.                         psurf->visxstart = x;
  1344.  
  1345.                         // Add the edge to the stack
  1346.                         psurf->pnext = psurf2;
  1347.                         psurf2->pprev = psurf;
  1348.                         surfstack.pnext = psurf;
  1349.                         psurf->pprev = &surfstack;
  1350.                     }
  1351.                     else
  1352.                     {
  1353.                         // Not a new top; sort into the surface stack.
  1354.                         // Guaranteed to terminate due to sentinel
  1355.                         // background surface
  1356.                         do
  1357.                         {
  1358.                             psurf2 = psurf2->pnext;
  1359.                             zinv2 = psurf2->zinv00 +
  1360.                                     psurf2->zinvstepx * fx +
  1361.                                     psurf2->zinvstepy * fy;
  1362.                         } while (zinv < zinv2);
  1363.  
  1364.                         // Insert the surface into the stack
  1365.                         psurf->pnext = psurf2;
  1366.                         psurf->pprev = psurf2->pprev;
  1367.                         psurf2->pprev->pnext = psurf;
  1368.                         psurf2->pprev = psurf;
  1369.                     }
  1370.                 }
  1371.             }
  1372.             else
  1373.             {
  1374.                 // It's a trailing edge; if this was the top surface,
  1375.                 // emit the span and remove it.
  1376.                 // First, make sure the edges didn't cross
  1377.                 if (--psurf->state == 0)
  1378.                 {
  1379.                     if (surfstack.pnext == psurf)
  1380.                     {
  1381.                         // It's on top, emit the span
  1382.                         x = ((pedge->x + 0xFFFF) >> 16);
  1383.                         pspan->count = x - psurf->visxstart;
  1384.                         if (pspan->count > 0)
  1385.                         {
  1386.                             pspan->y = y;
  1387.                             pspan->x = psurf->visxstart;
  1388.                             pspan->color = psurf->color;
  1389.  
  1390.                             // Make sure we don't overflow
  1391.                             // the span array
  1392.                             if (pspan < &spans[MAX_SPANS])
  1393.                                 pspan++;
  1394.                         }
  1395.  
  1396.                         psurf->pnext->visxstart = x;
  1397.                     }
  1398.  
  1399.                     // Remove the surface from the stack
  1400.                     psurf->pnext->pprev = psurf->pprev;
  1401.                     psurf->pprev->pnext = psurf->pnext;
  1402.                 }
  1403.             }
  1404.         }
  1405.  
  1406.         // Remove edges that are done
  1407.         pedge = removeedges[y];
  1408.         while (pedge)
  1409.         {
  1410.             pedge->pprev->pnext = pedge->pnext;
  1411.             pedge->pnext->pprev = pedge->pprev;
  1412.             pedge = pedge->pnextremove;
  1413.         }
  1414.  
  1415.         // Step the remaining edges one scan line, and re-sort
  1416.         for (pedge=edgehead.pnext ; pedge != &edgetail ; )
  1417.         {
  1418.             ptemp = pedge->pnext;
  1419.  
  1420.             // Step the edge
  1421.             pedge->x += pedge->xstep;
  1422.  
  1423.             // Move the edge back to the proper sorted location,
  1424.             // if necessary
  1425.             while (pedge->x < pedge->pprev->x)
  1426.             {
  1427.                 pedge2 = pedge->pprev;
  1428.                 pedge2->pnext = pedge->pnext;
  1429.                 pedge->pnext->pprev = pedge2;
  1430.                 pedge2->pprev->pnext = pedge;
  1431.                 pedge->pprev = pedge2->pprev;
  1432.                 pedge->pnext = pedge2;
  1433.                 pedge2->pprev = pedge;
  1434.             }
  1435.  
  1436.             pedge = ptemp;
  1437.         }
  1438.     }
  1439.  
  1440.     pspan->x = -1;  // mark the end of the list
  1441. }
  1442.  
  1443. /////////////////////////////////////////////////////////////////////
  1444. // Draw all the spans that were scanned out.
  1445. /////////////////////////////////////////////////////////////////////
  1446. void DrawSpans (void)
  1447. {
  1448.     span_t  *pspan;
  1449.  
  1450.     for (pspan=spans ; pspan->x != -1 ; pspan++)
  1451.     {
  1452.         memset (pDIB + (DIBPitch * pspan->y) + pspan->x,
  1453.                 pspan->color,
  1454.                 pspan->count);
  1455.     }
  1456. }
  1457.  
  1458. /////////////////////////////////////////////////////////////////////
  1459. // Clear the lists of edges to add and remove on each scan line.
  1460. /////////////////////////////////////////////////////////////////////
  1461. void ClearEdgeLists(void)
  1462. {
  1463.     int i;
  1464.  
  1465.     for (i=0 ; i<DIBHeight ; i++)
  1466.     {
  1467.         newedges[i].pnext = &maxedge;
  1468.         removeedges[i] = NULL;
  1469.     }
  1470. }
  1471.  
  1472. /////////////////////////////////////////////////////////////////////
  1473. // Render the current state of the world to the screen.
  1474. /////////////////////////////////////////////////////////////////////
  1475. void UpdateWorld()
  1476. {
  1477.     HPALETTE        holdpal;
  1478.     HDC             hdcScreen, hdcDIBSection;
  1479.     HBITMAP         holdbitmap;
  1480.     polygon2D_t     screenpoly;
  1481.     polygon_t       *ppoly, tpoly0, tpoly1, tpoly2;
  1482.     convexobject_t  *pobject;
  1483.     int             i, j, k;
  1484.     plane_t         plane;
  1485.     point_t         tnormal;
  1486.  
  1487.     UpdateViewPos();
  1488.     SetUpFrustum();
  1489.     ClearEdgeLists();
  1490.     pavailsurf = surfs;
  1491.     pavailedge = edges;
  1492.  
  1493.  
  1494.     // Draw all visible faces in all objects
  1495.     pobject = objecthead.pnext;
  1496.  
  1497.     while (pobject != &objecthead)
  1498.     {
  1499.         ppoly = pobject->ppoly;
  1500.  
  1501.         for (i=0 ; i<pobject->numpolys ; i++)
  1502.         {
  1503.             // Move the polygon relative to the object center
  1504.             tpoly0.numverts = ppoly[i].numverts;
  1505.             for (j=0 ; j<tpoly0.numverts ; j++)
  1506.             {
  1507.                 for (k=0 ; k<3 ; k++)
  1508.                     tpoly0.verts[j].v[k] = ppoly[i].verts[j].v[k] +
  1509.                             pobject->center.v[k];
  1510.             }
  1511.  
  1512.             if (PolyFacesViewer(&tpoly0, &ppoly[i].plane))
  1513.             {
  1514.                 if (ClipToFrustum(&tpoly0, &tpoly1))
  1515.                 {
  1516.                     currentcolor = ppoly[i].color;
  1517.                     TransformPolygon (&tpoly1, &tpoly2);
  1518.                     ProjectPolygon (&tpoly2, &screenpoly);
  1519.  
  1520.                     // Move the polygon's plane into viewspace
  1521.                     // First move it into worldspace (object relative)
  1522.                     tnormal = ppoly[i].plane.normal;
  1523.                     plane.distance = ppoly[i].plane.distance +
  1524.                         DotProduct (&pobject->center, &tnormal);
  1525.                     // Now transform it into viewspace
  1526.                     // Determine the distance from the viewpont
  1527.                     plane.distance -=
  1528.                           DotProduct (¤tpos, &tnormal);
  1529.                     // Rotate the normal into view orientation
  1530.                     plane.normal.v[0] =
  1531.                             DotProduct (&tnormal, &vright);
  1532.                     plane.normal.v[1] =
  1533.                             DotProduct (&tnormal, &vup);
  1534.                     plane.normal.v[2] =
  1535.                             DotProduct (&tnormal, &vpn);
  1536.  
  1537.                     AddPolygonEdges (&plane, &screenpoly);
  1538.                 }
  1539.             }
  1540.         }
  1541.  
  1542.         pobject = pobject->pnext;
  1543.     }
  1544.  
  1545.     ScanEdges ();
  1546.     DrawSpans ();
  1547.  
  1548.     // We've drawn the frame; copy it to the screen
  1549.     hdcScreen = GetDC(hwndOutput);
  1550.     holdpal = SelectPalette(hdcScreen, hpalDIB, FALSE);
  1551.     RealizePalette(hdcScreen);
  1552.  
  1553.     hdcDIBSection = CreateCompatibleDC(hdcScreen);
  1554.     holdbitmap = SelectObject(hdcDIBSection, hDIBSection);
  1555.  
  1556.     BitBlt(hdcScreen, 0, 0, DIBWidth, DIBHeight, hdcDIBSection,
  1557.            0, 0, SRCCOPY);
  1558.  
  1559.     SelectPalette(hdcScreen, holdpal, FALSE);
  1560.     ReleaseDC(hwndOutput, hdcScreen);
  1561.     SelectObject(hdcDIBSection, holdbitmap);
  1562.     DeleteDC(hdcDIBSection);
  1563. }
  1564.